package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class leetcode101.graph.Code1
 * @Description 69. Sqrt(x)
 *
 * Given a non-negative integer x, compute and return the square root of x.
 *
 * Since the return type is an integer, the decimal digits are truncated,
 * and only the integer part of the result is returned.
 * Example 1:
 *
 * Input: x = 4
 * Output: 2
 * Example 2:
 *
 * Input: x = 8
 * Output: 2
 * Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
 *
 * Constraints:
 *
 * 0 <= x <= 231 - 1
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-28 9:52
 */
public class Code1 {
    public int mySqrt(int x) {
        long tempt = x;
        if (x == 0) {
            return 0;
        }
        if (x == 1 || x == 2 || x == 3) {
            return 1;
        }

        long low = 1;
        long high = x / 2;
        long mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (mid * mid < x) {
                low = mid + 1;
            }
            if (mid * mid == x) {
                return (int) mid;
            }
            if (mid * mid > x) {
                high = mid - 1;
            }
        }
        return (int) (low - 1);
    }
}
